.TH cheetah 1
.SH NAME
cheetah \- Single-pass simulator for direct-mapped, set-associative and fully
associative caches.
.SH SYNTAX
.B cheetah
[
.B \-options
]
.SH DESCRIPTION
.I cheetah
is a cache simulation package which can simulate various cache
configurations.
It is a collection of single-pass simulators which simulate ranges of
direct-mapped,  set-associative and fully-associative caches.
The input to
.I cheetah
is a memory address trace in one of three formats:
.PP
(i) A binary format where the trace is a sequence of four
byte addresses.
This is the format that is actually used in the simulator,
and hence no internal
conversion step is required. If the trace format you have is
not among those supported
by
.I cheetah
it is most efficient to convert it to the binary format
for use with
.I cheetah.
.PP
(ii) The pixie format, where the trace is as output by the 
.I pixie
tool available on MIPS processor based workstations.
.PP
(iii) The
.I DIN
format, developed by Mark Hill, and used by earlier
cache simulators such as
.I Tycho
and
.I Dinero III.
.PP
.I cheetah
outputs the miss ratios of the various caches simulated.
.PP
.I cheetah
uses efficient single-pass simulation algorithms, and so
in each simulation
run it can determine the miss-ratios of a range of cache configurations.
It exploits inclusion and other relations that hold between cache configurations
to significantly speedup the simulation.
When many cache configurations need to be simulated on several traces
the use of
.I cheetah
should greatly improve the efficiency of the process over
running a large number of simulations with simple one-cache-at-a-time
simulators.
.I Tycho
(Mark Hill 1989)
is an earlier cache simulation package that also used single-pass simulation
algorithms for simulating multiple LRU set-associative caches. The
capabilities of
.I cheetah
are a superset of those of Tycho. Further, the algorithm
that
.I cheetah
uses to simulate set-associative caches is more efficient
both in terms of simulation time and memory requirements that the one used
in Tycho.
.PP
.I cheetah
can simulate caches under LRU and OPT replacement strategies.
With OPT replacement the set-associative simulators permit cache bypass.
That is, on a miss the referenced line is installed in cache only if its
priority is high enough.
OPT replacement is done by doing a limited look-ahead in the trace and
fixing errors in the stack using a stack repair procedure.
.PP
For further details on the algorithms used in
.I cheetah
please see the publications
referenced below.
.PP
.SH OPTIONS
(If the option is not specified, the corresponding parameter takes
a default value in all cases.)
.PP
.I cheetah
has four major options which set the replacement strategy, the cache configuration,
the trace format and the trace type.
.TP 5
.BI \-R repl
Used to specify the replacement strategy.
Replacement policies that are currently supported are
.I lru
and
.I opt.
(default 
.I lru
)
.TP 5
.BI \-C config
Used to specify the configuration. Configuration can be one of
.RS
.TP 10
.I fa
Simulate fully-associative caches.
.TP
.I sa
Simulate set-associative caches.
.TP
.I dm
Simulate direct-mapped caches.
Direct\-mapped should be specified only if direct\-mapped
caches of varying line sizes
but constant size need to be simulated. Direct\-mapped caches of varying sizes
may be simulated by setting the configuration to set-associative and the maximum
associativity to one.
.PP
The default configuration is
.I sa.
.RE
.TP 5
.BI \-F format
Used to specify the trace format. Currently, the trace format can be one of
.RS
.TP 10
.I pixie
Trace as generated by pixie.
.TP
.I din
Trace in the DIN format (Mark Hill).
.TP
.I basic
Trace is a sequence of four byte addresses.
.PP
The default format is
.I basic.
.RE
.TP 5
.BI \-T type
Used to specify the trace type.
.I i[nstruction]
for instruction traces,
.I d[ata]
for data traces and 
.I u[nified]
for unified instruction and data traces may be
specified. This option is ignored for the basic trace format.
The default trace type is
.I unified.
.PP
Along with the above four major options,
for each configuration a set of options are recognized that serve
to set various parameter values.
Options that are valid for all configurations are first described, followed
by the specific options for each of the three configurations.
.PP
The following options are used for all configurations and set the input/output
files and other global simulation parameters.
.TP 5
.BI \-t number
Specifies an upper limit on the number of addresses processed (default 1 billion).
.TP
.BI \-f file
Specifies the input file (default stdin).
.TP
.BI \-o file
Specifies the output file (default stdout).
.TP
.BI \-p number
Specifies the intervals at which simulation progress should be printed.
Useful for checking the status of the simulation (default 10 million).
.TP
.BI \-s number
Specifies the intervals at which intermediate results should be saved to the
output file.
.PP
The following options are used when the configuration is
set-associative to set parameter values and ranges.
All logs are to base 2.
.TP 5
.BI \-a number
Specifies the log of the minimum number of sets (default 7).
.TP
.BI \-b number
Specifies the log of the maximum number of sets (default 14).
.TP
.BI \-l number
Specifies the log of the line size of the caches (default 4).
.TP
.BI \-n number
Specifies the log of the maximum degree of associativity (default 1).
.PP
The following options are used when the configuration is fully-associative
to set parameter values.
.TP 5
.BI \-l number
Specifies the log of the line size of the caches (default 4).
.TP
.BI \-i number
Specifies the cache size intervals at which the miss ratio is desired
If this is less than the line size it is set to the line size (default 512 bytes).
.TP
.BI \-M number
Specifies the maximum cache size of interest.
When the contents of the stack go beyond this limit entries
are deleted from the bottom of the stack. This is primarily to
avoid thrashing (default 512 Kbytes).
.PP
The following options are used when the configuration is
direct-mapped to set parameter values
.TP 5
.BI \-a number
Specifies the log of the minimum line size (default 7).
.TP
.BI \-b number
Specifies the log of the maximum line size (default 14).
.TP
.BI \-c number
Specifies the log of the cache size (default 16).
.PP
.SH EXAMPLE
cheetah -Csa -Fbasic -Tu -Rlru -a5 -b14 -l4 -n2 -t1000000 -ftfile -oresults
.PP
Determines the miss ratios of set-associative caches with number of sets
ranging from 32 (2^5) to 16384 (2^14), and associativities ranging from
1 to 4 (2^2), with a line size of 16 (2^4) bytes.
The input trace format is 
.I basic
and is read from the file
.I tfile.
A unified instruction and data cache is simulated on the
first 1 million addresses in the trace.
The output is written to the file
.I results.
.PP
.SH BUGS
Currently,
.I cheetah
cannot handle traces that are longer than
2^31 addresses.
.PP
With OPT replacement, the memory requirement is not bounded, and thrashing
might occur with some traces.
.PP
The conversion routine for DIN traces is simple and not very efficient.
If you use DIN traces often it would help to make this routine
more efficient.
.PP
The package has not been thoroughly debugged on 64-bit architectures such
as the KSR and the DEC Alpha.
.PP
.SH AUTHORS
Rabin A. Sugumar (rabin@eecs.umich.edu) and Santosh G. Abraham (sga@eecs.umich.edu),
The University of Michigan.
.PP
.SH SEE ALSO
pixie (1), dineroIII ()
.PP
Rabin A. Sugumar and Santosh G. Abraham, ``Efficient Simulation of Caches using
Binomial Trees'', Technical Report CSE TR-111-91, University of Michigan, 1991.
.PP
Rabin A. Sugumar and Santosh G. Abraham, ``Efficient Simulation of Caches under
OPT replacement with Applications to Miss Characterization,'' in the proceedings
of the 1993 ACM SIGMETRICS Conference.

